/**
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
// 
// 
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
// 
//
// 示例 2： 
//
// 
//输入：head = [1,2]
//输出：[2,1]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目范围是 [0, 5000] 
// -5000 <= Node.val <= 5000 
// 
//
// 
//
// 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？ 
// 
// 
// Related Topics 递归 链表 👍 1933 👎 0

*/

package com.xixi.easy;

import com.xixi.dataStructure.lineList.ListNode;

public class ID00206ReverseLinkedList {
public static void main(String[] args) {
Solution solution = new ID00206ReverseLinkedList().new Solution();
}

    /**
     * 递归
     *
     * 1 -> 2 -> 3 -> 4 -> 5 -> null
     * @param head
     * @return
     */
    public ListNode digui(ListNode head){
        if(head == null || head.next == null){
            return head;
        }
        ListNode p = digui(head.next); //指针最后返回的是节点5，则当时的head是节点4；
        head.next.next = head; //让节点5.next = 节点4
        head.next = null; //节点4断链，指向null，避免循环指针
        return p; //返回的还是5，新链表头部
    }

    /**
     * 递归做法
     * @param head
     * @return
     */

    public ListNode newHead = new ListNode();
    public ListNode reverseList(ListNode head){

        ListNode prve = head;
        digui(prve, head.next);

        return newHead.next;
    }

    public void digui(ListNode prev, ListNode p) {
        if(p.next == null){ //终止条件
            newHead.next = p;
        }
        digui(p, p.next);
            p.next = prev;

    }


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

        if(head == null || head.next == null ) return  head;
        //头插
        ListNode newHead = new ListNode(0, null);//虚拟头节点
        ListNode p = head;
        ListNode deal ;

        while(p != null){
            deal = p; //赋值deal当前节点，以防原链表断链,因为deal.next的值会变
            p = p.next; //原链表位移
            deal.next = newHead.next; //新节点指向新链表头部
            newHead.next = deal; //新节点成为头部

        }

        return newHead.next;



    }
}
//leetcode submit region end(Prohibit modification and deletion)




}